package sort

import (
	"math/rand"
)

type BinarySort struct {
}

func NewBinarySort() *BinarySort {
	return &BinarySort{}
}

func (b *BinarySort) Sort(nums []int) []int {
	if len(nums) > 1 {
		b.sort(nums, 0, len(nums)-1)
	}
	return nums
}

func (b *BinarySort) sort(nums []int, l, r int) {
	//这里的退出条件为啥是大于等于，因为大于等于表示的是已经没有可以用来区分的三部分了，所以这部分可以跳过了。
	//当l == r的时候 mid = l = r 所以在mid那份就可以完成的比较好
	if l >= r {
		return
	}

	mid := b.partition(nums, l, r)
	b.sort(nums, l, mid-1)
	b.sort(nums, mid+1, r)
}

func (b *BinarySort) partition(nums []int, l, r int) int {
	//优化 随机的抽取一个中点进行比较
	p := rand.Intn(r - l + 1)
	nums[r], nums[l+p] = nums[l+p], nums[r]
	c := nums[r]
	j := l
	for i := l; i < r; i++ {
		if nums[i] < c {
			nums[i], nums[j] = nums[j], nums[i]
			j++
		}
	}
	nums[r], nums[j] = nums[j], nums[r]
	return j
}
